Papers with quadratic computational complexity
Finetuning LLMs for Comparative Assessment Tasks (2025.coling-main)
Copied to clipboard
| Challenge: | Automated assessment in natural language generation is a challenging task. |
| Approach: | They propose a framework for fine-tuning LLMs for comparative assessment to align the model’s output with the target distribution of comparative probabilities. |
| Outcome: | The proposed framework improves state-of-the-art performance while maintaining high performance with an efficient subset of comparisons. |
Scaling up the State Size of RNN LLMs for Long-Context Scenarios (2025.acl-long)
Copied to clipboard
| Challenge: | Existing RNN-based LLMs struggle with long-context scenarios due to their quadratic computational complexity and linear memory requirements. |
| Approach: | They propose an efficient scaling method to scale RNN models to match the 2k context length of Transformers with small parameters overhead. |
| Outcome: | The proposed method improves long-context understanding and improves performance on FDA recall-intensive tasks. |
TokenSelect: Efficient Long-Context Inference and Length Extrapolation for LLMs via Dynamic Token-Level KV Cache Selection (2025.emnlp-main)
Copied to clipboard
| Challenge: | Rapid advances in Large Language Models have spurred demand for processing extended context sequences . however, performance degradation due to sequence lengths out-of-distribution and excessively long inference times are limiting LLMs in long-context scenarios. |
| Approach: | They propose a training-free method for efficient and accurate long-context inference . they selectively involves a few critical KV cache tokens in attention calculation . |
| Outcome: | The proposed method speeds up attention computation and accelerates inference time while reducing selection overhead. |
LAWCAT: Efficient Distillation from Quadratic to Linear Attention with Convolution across Tokens for Long Context Modeling (2025.findings-emnlp)
Copied to clipboard
Zeyu Liu, Souvik Kundu, Lianghao Jiang, Anni Li, Srikanth Ronanki, Sravan Babu Bodapati, Gourav Datta, Peter Anthony Beerel
| Challenge: | a novel linearization framework is proposed to reduce the cost of training transformers from scratch. |
| Approach: | They propose a linear attention framework that integrates pre-trained transformers into a performant linear attention architecture. |
| Outcome: | The proposed framework improves performance on mistral-7B with 1K-length sequences and BABILong benchmarks. |
IRIS: Interpretable Retrieval-Augmented Classification for Long Interspersed Document Sequences (2025.acl-long)
Copied to clipboard
| Challenge: | Existing models for document classification struggle with long-text processing due to quadratic computational complexity in the self-attention module. |
| Approach: | They propose a framework that utilizes retrieval to efficiently classify long documents . they use a quadratic attention matrix to capture dependencies between tokens in an input sequence . |
| Outcome: | The proposed framework excels in clinical note disease risk prediction tasks . it can process arbitrarily long documents without increasing computational cost and trainable on a single GPU. |